<html>

<head>
<title>Wildcard Patterns</title>
</head>

<body>

<center>
<h1>CEOI 2001 Day 2 Problem 2</h1>
<h1>Wildcard Patterns</h1>
</center>

    <p ALIGN="JUSTIFY">Wildcard patterns are
    frequently used to specify sets of names. For example, we can specify all
    file names which start with <b>h</b> and end with <b>bak</b> by the pattern <b>h*bak</b>.</p>
    <p ALIGN="JUSTIFY">A <i>wildcard pattern</i> is
    a string that may contain * characters as wildcards. A string <b><i>W</i></b>
    matches a pattern <b><i>P</i></b> if <b><i>W</i></b> can be obtained from <b><i>P</i></b>
    by substituting some (possibly empty) string for each * character in <b><i>P</i></b>.
    (Different strings may be substituted for different occurrences of *.) For a
    pair of patterns <b><i>P<sub>1</sub></i></b> and <b><i>P<sub>2</sub>,</i></b>
    <b><i>Q</i></b> is a <i>common pattern</i> of <b><i>P<sub>1</sub></i></b>
    and <b><i>P<sub>2</sub></i></b> if any string that matches <b><i>Q</i></b>
    also matches both <b><i>P<sub>1</sub></i></b> and <b><i>P<sub>2</sub></i></b>.</p>
    <p ALIGN="JUSTIFY">A set <b><i>Q<sub>1</sub></i></b>,
    <b><i>Q<sub>2</sub></i></b>, &#8230;, <b><i>Q<sub>L </sub></i></b>of common
    patterns is called <i>complete</i> if any string that matches both <b><i>P<sub>1</sub></i></b>
    and <b><i>P<sub>2 </sub></i></b>matches at least one <b><i>Q<sub>i</sub></i></b>
    (1&lt;=<b><i>i&lt;=</i></b><b><i>L</i></b>).</p>
    <p ALIGN="JUSTIFY">You are to write a program
    that for a given pair of patterns <b><i>P<sub>1</sub></i></b> and <b><i>P<sub>2</sub></i></b>
    computes</p>
    <ol TYPE="A">
      <li>at least one common pattern (but no wrong
        patterns); or</li>
      <li>a complete set of common patterns with no
        more than 6666 entry; or</li>
      <li>a complete set of common patterns which is
        minimal in the number of elements (i.e. there is no smaller set of
        common patterns, which is complete) Note that solving this task you will
        earn <b>100% plus an additional</b> <b>50% of the scores</b>.</li>
    </ol>
    <h2>Input</h2>
    <p ALIGN="JUSTIFY">The first and the second
    lines of the file pattern.in contain the patterns <b><i>P<sub>1</sub></i></b>
    and <b><i>P<sub>2</sub></i></b>. The patterns are composed of the lowercase
    letters from &#8216;a&#8217; to &#8216;z&#8217; and the &#8216;*&#8217;
    character. Each pattern contains no more than 20 characters. The number of
    the * characters in each pattern is between 0 and 6.</p>
    <h2>Output</h2>
    <p ALIGN="JUSTIFY">The first line of the file
    pattern.out must contain the integer <b><i>K</i></b>, the number of common
    patterns computed as a solution. The next <b><i>K</i></b> lines contain one
    common pattern in each line; these constitute the solution.</p>
    <p ALIGN="JUSTIFY">The order of the common
    patterns is irrelevant. Both case B and C can be solved within the specified
    limit of 6666 entries. If there is no common pattern of <b><i>P<sub>1</sub></i></b>
    and <b><i>P<sub>2</sub></i></b>, then the first and only line must contain
    the number 0.</p>
    <h2>Example</h2>
    <table BORDER="1" CELLSPACING="1" CELLPADDING="1" WIDTH="568">
      <tr>
        <td WIDTH="50%" VALIGN="TOP">pattern.in</td>
        <td WIDTH="50%" VALIGN="TOP">pattern.out (for case C)</td>
      </tr>
      <tr>
        <td WIDTH="50%" VALIGN="TOP">
          *ab*<br>
          ba*b</td>
        <td WIDTH="50%" VALIGN="TOP">
          4<br>
          ba*ab*b<br>
          bab*b<br>
          ba*ab<br>
          bab<br>
      </tr>
    </table>
    <h2>Grading</h2>
    <p ALIGN="JUSTIFY">If your solution solves case
    A then you obtain 5 points. If your solution solves case B then you obtain
    10 points. If your solution solves case C then you obtain 15 points.</p>
    </td>
  </tr>
</table>
</div>
</body>

</html>
